package com.qch.edu.lagou.graph.graphTable;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * @Author qch
 * @Date 2021/7/22
 * 邻接表实现
 */
public class Graph2 {
    Map<String, Vertex> vertexMap = new HashMap<String, Vertex>();//存储顶点

    //插入顶点
    public void insertVertex(String name) {
        Vertex vertex = new Vertex(name, null);
        vertexMap.put(name, vertex);
    }

    ;

    public void insertEdge(String start, String end, int weight) {
        Vertex vstart = vertexMap.get(start);
        if (vstart == null) {
            return;//没有顶点不许插入边
        }
        Edge edge = new Edge(end, weight, null);
        //无边
        if (vstart.next == null) {
            vstart.next = edge;
        } else {
            //有边，循环找到最后一条边
            Edge last = vstart.next;
            while (last.next!= null) {
                last = last.next;
            }
            last.next = edge;
        }
    }

    /**
     * 打印图
     */
    public void print() {
        Set<Map.Entry<String, Vertex>> entries = vertexMap.entrySet();
        Iterator<Map.Entry<String, Vertex>> iterator = entries.iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Vertex> entry = iterator.next();
            Vertex vertex = entry.getValue();
            Edge edge = vertex.next;
            while (edge != null) {
                System.out.println(vertex.name + "指向" + edge.name + "权值：" + edge.weight);
                edge = edge.next;
            }

        }
    }

    public static void main(String[] args) {
        Graph2 graph = new Graph2();
        graph.insertVertex("A");
        graph.insertVertex("B");
        graph.insertVertex("C");
        graph.insertVertex("D");
        graph.insertVertex("E");
        graph.insertVertex("F");
        graph.insertEdge("A", "B", 4);
        graph.insertEdge("A", "D", 5);
        graph.insertEdge("C", "A", 1);
        graph.insertEdge("D", "E", 3);
        graph.insertEdge("D", "F", 4);
        graph.insertEdge("E", "B", 2);
        graph.insertEdge("F", "C", 2);

        graph.print();
    }
}
